package stack_queue.oj;

import java.util.*;

public class NumNk52 {
    //约瑟夫问题II
    public static int getResult(int n) {
        // n代表游戏的人数。请返回最后一个人的编号
        // write code here
        //因为涉及到较多的删除插入操作,所以选用链表来做
        List<Integer> list = new LinkedList<>();
        //将1-n个元素依次存入链表中,下标从1开始存,为了下标和元素一一对应
        for (int i = 1;i < n+1 ;i++){
            list.add(i);
        }
        //初始情况下步长为2:12121212....报数
        int steps = 2;
        //依次遍历链表中的元素,当数组只剩1个元素时停止遍历
        // 模拟报数,当其取余步长不为0时,就将其值改为-1.意味着其为要删除元素
        while (list.size() > 1){
            for (int i = 1; i < list.size();i++){
                if (i%steps != 0){
                    list.set(i,-1);
                }
            }
            Iterator<Integer> iterable = list.iterator();
            while (iterable.hasNext()){
                if (iterable.next() == -1){
                    iterable.remove();
                }
            }
            //调整新的步数123,123,123.....
            steps = steps+1;
            //将链表最后一个元素搬移到链表头部,模拟从最后一人开始报数
            ((LinkedList<Integer>) list).addFirst(list.get( list.size()-1));
            //删除最后一个元素,因为已经放到头部了
            list.remove( list.size()-1);
        }
        //当循环结束后,剩下的唯一一个1就会被搬移到链表的最前面,下标为0,返回他即可
        int num = list.get(0);
        return num;
    }

    public static void main(String[] args) {
        int index = getResult(13);
        System.out.println(index);
    }
}

